Кафедра: Автоматика та Інформаційні Технології
Структури та об'єднання
ЗМІСТ
Традиційний приклад структури - рядок платіжної відомості. Вона містить такі відомості про службовця, як його повне ім'я, адресу, номер картки соціального страхування, зарплата і т.д. Деякі з цих характеристик самі можуть бути структурами: наприклад, повне ім'я складається з декількох компонент (прізвища, імені та по батькові); аналогічно адресу, і навіть зарплата. Інший приклад (більш типовий для Сі) - з області графіки: точка є пара координат, прямокутник є пара крапок і т. д.
Головні зміни, внесені стандартом ANSI щодо структур, - це введення для них операції привласнення. Структури можуть копіюватися, над ними можуть виконуватися операції привласнення, їх можна передавати функцій як аргументи, а функції можуть повертати їх в якості результату. У більшості компіляторів вже давно реалізовані ці можливості, але тепер вони точно обумовлені стандартом. Для допускається ініціалізація.
struct імя_структури {
список оголошень;
};
імя_структури іноді називають тегом структури.
Перераховані в структурі змінні називаються елементами. Елементами структур можуть бути:
- Змінні та масиви базових типів,
- Змінні та масиви для користувача типів, крім типу самої структури імя_структури,
- Покажчики на будь-які типи, включаючи і тип самої структури імя_структури,
- Функції.
Включення до структури елементів-функцій не є загальноприйнятим. Як правило, в цьому випадку переходять до поняття класу.
Елементи структур є публічними, тобто до елементів структурних змінних можна звертатися в будь-якому місці області видимості цих змінних.
Наведемо приклад структури time:
struct time {
int hour;
int minutes;
};
У нашому прикладі елементами структури будуть hour і minutes.
Оголошення структури не резервує пам'яті. Воно є інформацією компілятору про введення користувальницького типу даних. Пам'ять виділиться при визначенні структурних змінних.
Якщо структурний тип в програмі більше не буде використовуватися, оголошують безіменну структуру одночасно з визначенням змінної. Наприклад,
struct {
int x, y;
} Q;
Однак якщо структура має тег, то цим тегом далі можна користуватися при визначенні структурних об'єктів. Наприклад, за допомогою заданого вище опису структури time рядок
struct time t;
визначає структурну змінну t типу struct time. Прийнято використовувати один і той же термін структура стосовно до призначеного для користувача типу даних і до структурної змінної. Однак, по фразах «оголошення структури» і «визначення структури» ситуація стає однозначною. Для структурної змінної, як і для масиву при оголошенні відразу виділяється пам'ять. Тому структурна змінна визначається, а тип оголошується.
Структурну змінну при її визначенні можна ініціалізувати, формуючи список ініціалізаторов її елементів у вигляді константних виразів. При цьому кожен елемент, що сам є структурою або масивом, ініціалізується окремою парою фігурних дужок. Доступ до окремого елементу структури здійснюється за допомогою бінарної операції «крапка». Офіційна назва цієї операції: звернення до елемента структури на ім'я структури. Синтаксис операції
Имя_структуры.элемент_структуры
Операція доступу до елементу структури '.' з'єднує ім'я структури і ім'я елемента.
Наприклад,
struct time t = {21, 30};
printf ("% d:% d", t.hour, t.minutes);
Структури можуть бути вкладені одна в одну. Наприклад, структура chronos містить дві структури time begin і end:
struct chronos {
struct time begin, end;
};
struct chronos timer = {{2,4}, {10, 10}};
Вираз timer.begin.minutes звертається до хвилин minutes часу begin з timer.
У стандарті ANSI C ключове слово struct при оголошенні структурних змінних можна опускати, тобто допустима і загальноприйнята запис.
chronos timer;
Розмір структури в байтах складається з розміру її елементів. Наприклад, sizeof (timer) = 8 байт. Однак, якщо включена опція компілятора Options-Compiler-Code generation-Word allgnment, то всі елементи будуть розташовуватися по парних адресами. Тому в разі
struct FIO {char F [25], I [15], Otch [20]};
будемо мати sizeof (FIO) = 26 + 16 + 20 = 62.
- Присвоєння,
- Взяття адреси за допомогою &,
- Здійснення доступу до її елементів.
Присвоєння використовується при передачі структури в функцію за значенням і повернення структури за значенням. Структури не можна порівнювати. Ініціалізувати структуру можна списком константних значень її елементів; автоматичну структуру також можна ініціалізувати присвоюванням.
Щоб краще познайомитися зі структурами, напишемо декілька функцій, які маніпулюють time і chronos. Виникає питання: а як передавати функцій названі об'єкти? Існує, принаймні, три підходи: передавати компоненти окремо, передавати всю структуру цілком і передавати покажчик на структуру. Кожен підхід має свої плюси і мінуси.
Перша функція, maketime, отримує два цілих значення та повертає структуру time.
/ * Maketime: формує час по компонентах hour і minutes * /
time maketime (int hour, int minutes) {
time temp;
temp.hour = hour;
temp.minutes = minutes;
return temp;
}
Зауважимо: ніякого конфлікту між ім'ям аргументу і ім'ям елемента структури не виникає, більше того, схожість підкреслює спорідненість позначаються їм об'єктів.
Тепер за допомогою maketime можна виконувати динамічну ініціалізацію структури або формувати структурні аргументи для тієї чи іншої функції:
chronos timer;
timer.begin = maketime (0, 0);
timer.end = maketime (12, 5);
Наступний крок полягає у визначенні ряду функцій, що реалізують різні операції над часом. В якості прикладу розглянемо наступну функцію:
/ * Addtime: додавання часу * /
time addtime (time tm1, time tm2)
{
tm1.minutes + = tm2.minutes;
tm1.hour + = tm2.hour + tm1.minutes/60;
tm1.minutes% = 60;
return tm1;
}
Тут обидва аргументи і повертається значення - структури.
В якості іншого прикладу наведемо функцію tinchronos, яка перевіряє: чи знаходиться даний момент часу всередині нашого інтервалу.
/ * Tinchronos: повертає 1, якщо t в c, і 0 у противному випадку * /
int tinchronos (struct time t, struct chronos c)
{
return t.hour> = c.begin.hour
& & T.hour <c.end.hour
& & T.minutes> = c.begin.minutes
& & T.minutes <c.end.minutes;
}
імя_структурного_тіпа * імя_указателя_на_структуру;
Якщо функції передається велика структура, те, чим копіювати її цілком, ефективніше передати вказівник на неї. Покажчики на структури нічим не відрізняються від покажчиків на звичайні змінні. Оголошення
time * pt;
повідомляє, що pt - це покажчик на структуру типу struct time. Якщо pt вказує на структуру time, то * pt - це сама структура, а (* pt). Hour і (* pt). Minutes - її елементи. Використовуючи покажчик pt, ми могли б написати
time origin, * pt;
pt = &origin;
printf ("origin: (% d,% d) \ n", (* pt). hour, (* pt). minutes);
Дужки в (* pt). Hour необхідні, оскільки пріоритет операції «." Вище, ніж пріоритет операції разименованія «*». Вираз * pt.hour буде проінтерпретувати як * (pt.hour), що невірно, оскільки pt.hour не є покажчиком.
Покажчики на структури використовуються дуже часто, тому для доступу до її елементів була придумана операція «звернення до елементу структури за вказівником», скорочено «стрілка» з формою запису «->». Якщо t - покажчик на структуру, то
t-> елемент-структури
є її окремий елемент. Тому printf можна переписати у вигляді
printf ("origin: (% d,% d) \ n", pt-> hour, pt-> minutes);
Операції. і -> левоассоціатівни, тобто виконуються зліва направо. Таким чином, при наявності оголошення
chronos ch, * cht = &ch;
наступні чотири вираження будуть еквівалентні:
ch.begin.hour
cht-> begin.hour
(Ch.begin). Hour
(Cht -> begin). Hour
Операції доступу до елементів структури. і -> разом з операторами виклику функції () та індексації масиву [] займають найвище положення в ієрархії пріоритетів та виконуються раніше будь-яких інших операторів. Наприклад, якщо задано оголошення
struct {
int len;
char * str;
} * P;
то
+ + P-> len
збільшить на 1 значення елемента структури len, а не покажчик p, оскільки в цьому виразі як би неявно присутні дужки: + + (p-> len). Щоб змінити порядок виконання операцій, потрібні явні дужки. Так, у (+ + р) -> len, перш ніж узяти значення len, програма збільшить покажчик p. В (р ++)-> len покажчик p збільшиться після того, як буде взято значення len (в останньому випадку дужки не обов'язкові).
За тими ж правилами * p-> str позначає вміст об'єкта, на який вказує str; * p-> str + + збільшить покажчик str після отримання значення об'єкта, на який він вказував (як і в вираженні * s + +), (* p-> str ) + + збільшить значення об'єкта, на який вказує str; * p + + -> str збільшить p після отримання того, на що вказує str.
Часто виникає проблема, при оголошенні структури оголосити там покажчик на цю ж структуру. Не дивлячись на те, що опис структури ще не завершено, формат мови це дозволяє. Наприклад, опишемо структуру List, що представляє собою односпрямований список, де в якості даних опишемо змінну типу int.
struct List {
int dat;
List * next;
};
Якщо структури містяться один в одному, то використовують предоб'явленіе структури. Наприклад
struct B;
struct A {B b;};
struct B {A a;};
Розглянемо приклад програми створює такий список і виводить його вміст на консоль.
# Include <stdio.h>
struct List
{
int dat;
List * next;
};
void main ()
{
int i;
List * p, * heap = new List;
for (p = heap, i = 0; i <10; i + +) {
p-> dat = i;
p = p-> next = new List;
}
for (p = heap, i = 0; i <10; i + +) {
printf ("% d", p-> dat);
p = p-> next;
}
}
Тут ми описали два покажчики: heap - для вказівки початку списку, p - для пересування за списком; і просту змінну, як лічильник циклу. На відміну від масиву, наш список буде "розкиданий" по пам'яті, оскільки оператор new виділяє перші вільні блоки пам'яті, але це неважливо, оскільки ми пересуваємося за списком, використовуючи збережені в самому списку адреси:
p = p-> next;.
char * keyword [NKEYS];
int keycount [NKEYS];
Однак саме той факт, що вони є паралельними, підказує нам іншу організацію зберігання - через масив структур. Кожне ключове слово можна описати парою характеристик
char * word;
int count;
Такі пари складають масив. Оголошення
struct key {
char * word;
int count;
} Keytab [NKEYS];
оголошує структуру типу key і визначає масив keytab, кожен елемент якого є структурою цього типу і якому десь буде виділена пам'ять. Це ж можна записати й по-іншому:
struct key {
char * word;
int count;
};
key keytab [NKEYS];
Так як keytab містить постійний набір імен, його найлегше зробити зовнішнім масивом і ініціалізувати один раз на момент визначення. Ініціалізація структур аналогічна раніше демонстрованих ініціалізації - за визначенням слід список ініціалізаторов, укладений у фігурні дужки:
struct key {
char * word;
int count;
} Keytab [] = {
"Auto", 0,
"Break", 0,
"Case", 0,
"Char", 0,
"Const", 0,
"Continue", 0,
"Default", 0,
/*...*/
"Unsigned", 0,
"Void", 0,
"Volatile", 0,
"While", 0
};
Ініціалізатор задаються парами, щоб відповідати конфігурації структури. Строго кажучи, пару ініціалізаторов для кожної окремої структури варто було б укласти у фігурні дужки, як, наприклад, в
{"Auto", 0},
{"Break", 0},
{"Case", 0},
...
Однак коли ініціалізатор - прості константи або рядки символів і всі вони є в наявності, у внутрішніх дужках немає необхідності. Кількість елементів масиву keytab буде обчислено за кількістю ініціалізаторов, оскільки вони представлені повністю, а всередині квадратних дужок "[]" нічого не задано.
Програма підрахунку ключових слів починається з визначення keytab. Програма main читає введення, багаторазово звертаючись до функції getword і отримуючи на кожному її виклику чергове слово. Кожне слово шукається в keytab. Для цього використовується функція бінарного пошуку. Список ключових слів повинен бути впорядкований в алфавітному порядку.
# Include <stdio.h>
# Include <ctype.h>
# Include <string.h>
# Define MAXWORD 100
int getword (char *, int);
int binsearch (char *, struct key *, int);
/ * Підрахунок ключових слів Сі * /
main ()
{
int n;
char word [MAXWORD];
while (getword (word, MAXWORD)! = EOF)
if (isalpha (word [0]))
if ((n = binsearch (word, keytab, NKEYS))> = 0)
keytab [n]. count + +;
for (n = 0; n <NKEYS; n + +)
if (keytab [n]. count> 0)
printf ("% 4d% s \ n", keytab [n]. count, keytab [n]. word);
return 0;
}
/ * Binsearch: знайти слово в tab [0] ... tab [n-1] * /
int binsearch (char * word, struct key tab [], int n)
{
int cond;
int low, high, mid;
low = 0;
high = n-1;
while (low <= high) {
mid = (low + high) / 2;
if ((cond = strcmp (word, tab [mid]. word)) <0)
high = mid - 1;
else if (cond> 0)
low = mid + 1;
else
return mid;
}
return -1;
}
Трохи пізніше ми розглянемо функцію getword, а зараз нам досить знати, що при кожному її виклику виходить чергове слово, яке запам'ятовується в масиві, заданому першим аргументом.
NKEYS - кількість ключових слів у keytab. Хоча ми могли б підрахувати число таких слів вручну, набагато легше і безпечніше зробити це з допомогою машини, особливо якщо список ключових слів може бути змінений. Одне з можливих рішень - помістити в кінець списку ініціалізаторов порожній покажчик (NULL) і потім перебирати в циклі елементи keytab, поки не зустрінеться кінцевий елемент.
Але можливе й більш просте рішення. Оскільки розмір масиву повністю визначений під час компіляції і дорівнює добутку кількості елементів масиву на розмір його окремого елемента, число елементів масиву можна обчислити за формулою
розмір keytab / розмір struct key
У Сі є унарна операція sizeof, яка працює під час компіляції. Його можна застосовувати для обчислення розміру будь-якого об'єкта. Вирази
sizeof об'єкт
і
sizeof (ім'я типу)
Структури та об'єднання
ЗМІСТ
1. СТРУКТУРИ
Основні відомості про структури
Структури та функції
Покажчики на структури
Масиви структур
2. ОБ'ЄДНАННЯ
3. ПРАКТИЧНІ ЗАВДАННЯ
Завдання 3.1
Завдання 3.2.
Завдання 3.3.
4. ЛАБОРАТОРНІ ЗАВДАННЯ
5. ДОДАТКОВІ ЗАВДАННЯ
Завдання 5.1.
Завдання 5.2.
Завдання 5.3.
СПИСОК
1. Структури
Структура - це іменована сукупність змінних можливо різних типів, розташована в пам'яті послідовно один за одним. Структури називаються користувача типами даних і допомагають в організації складних даних, оскільки дозволяють групу пов'язаних між собою змінних трактувати не як безліч окремих елементів, а як єдине ціле.Традиційний приклад структури - рядок платіжної відомості. Вона містить такі відомості про службовця, як його повне ім'я, адресу, номер картки соціального страхування, зарплата і т.д. Деякі з цих характеристик самі можуть бути структурами: наприклад, повне ім'я складається з декількох компонент (прізвища, імені та по батькові); аналогічно адресу, і навіть зарплата. Інший приклад (більш типовий для Сі) - з області графіки: точка є пара координат, прямокутник є пара крапок і т. д.
Головні зміни, внесені стандартом ANSI щодо структур, - це введення для них операції привласнення. Структури можуть копіюватися, над ними можуть виконуватися операції привласнення, їх можна передавати функцій як аргументи, а функції можуть повертати їх в якості результату. У більшості компіляторів вже давно реалізовані ці можливості, але тепер вони точно обумовлені стандартом. Для допускається ініціалізація.
Основні відомості про структури
Оголошення структури починається з ключового слова struct і містить список оголошень, укладений у фігурні дужки:struct імя_структури {
список оголошень;
};
імя_структури іноді називають тегом структури.
Перераховані в структурі змінні називаються елементами. Елементами структур можуть бути:
- Змінні та масиви базових типів,
- Змінні та масиви для користувача типів, крім типу самої структури імя_структури,
- Покажчики на будь-які типи, включаючи і тип самої структури імя_структури,
- Функції.
Включення до структури елементів-функцій не є загальноприйнятим. Як правило, в цьому випадку переходять до поняття класу.
Елементи структур є публічними, тобто до елементів структурних змінних можна звертатися в будь-якому місці області видимості цих змінних.
Наведемо приклад структури time:
struct time {
int hour;
int minutes;
};
У нашому прикладі елементами структури будуть hour і minutes.
Оголошення структури не резервує пам'яті. Воно є інформацією компілятору про введення користувальницького типу даних. Пам'ять виділиться при визначенні структурних змінних.
Якщо структурний тип в програмі більше не буде використовуватися, оголошують безіменну структуру одночасно з визначенням змінної. Наприклад,
struct {
int x, y;
} Q;
Однак якщо структура має тег, то цим тегом далі можна користуватися при визначенні структурних об'єктів. Наприклад, за допомогою заданого вище опису структури time рядок
struct time t;
визначає структурну змінну t типу struct time. Прийнято використовувати один і той же термін структура стосовно до призначеного для користувача типу даних і до структурної змінної. Однак, по фразах «оголошення структури» і «визначення структури» ситуація стає однозначною. Для структурної змінної, як і для масиву при оголошенні відразу виділяється пам'ять. Тому структурна змінна визначається, а тип оголошується.
Структурну змінну при її визначенні можна ініціалізувати, формуючи список ініціалізаторов її елементів у вигляді константних виразів. При цьому кожен елемент, що сам є структурою або масивом, ініціалізується окремою парою фігурних дужок. Доступ до окремого елементу структури здійснюється за допомогою бінарної операції «крапка». Офіційна назва цієї операції: звернення до елемента структури на ім'я структури. Синтаксис операції
Имя_структуры.элемент_структуры
Операція доступу до елементу структури '.' з'єднує ім'я структури і ім'я елемента.
Наприклад,
struct time t = {21, 30};
printf ("% d:% d", t.hour, t.minutes);
Структури можуть бути вкладені одна в одну. Наприклад, структура chronos містить дві структури time begin і end:
struct chronos {
struct time begin, end;
};
struct chronos timer = {{2,4}, {10, 10}};
Вираз timer.begin.minutes звертається до хвилин minutes часу begin з timer.
У стандарті ANSI C ключове слово struct при оголошенні структурних змінних можна опускати, тобто допустима і загальноприйнята запис.
chronos timer;
Розмір структури в байтах складається з розміру її елементів. Наприклад, sizeof (timer) = 8 байт. Однак, якщо включена опція компілятора Options-Compiler-Code generation-Word allgnment, то всі елементи будуть розташовуватися по парних адресами. Тому в разі
struct FIO {char F [25], I [15], Otch [20]};
будемо мати sizeof (FIO) = 26 + 16 + 20 = 62.
Структури та функції
Над структурами можливі наступні операції:- Присвоєння,
- Взяття адреси за допомогою &,
- Здійснення доступу до її елементів.
Присвоєння використовується при передачі структури в функцію за значенням і повернення структури за значенням. Структури не можна порівнювати. Ініціалізувати структуру можна списком константних значень її елементів; автоматичну структуру також можна ініціалізувати присвоюванням.
Щоб краще познайомитися зі структурами, напишемо декілька функцій, які маніпулюють time і chronos. Виникає питання: а як передавати функцій названі об'єкти? Існує, принаймні, три підходи: передавати компоненти окремо, передавати всю структуру цілком і передавати покажчик на структуру. Кожен підхід має свої плюси і мінуси.
Перша функція, maketime, отримує два цілих значення та повертає структуру time.
/ * Maketime: формує час по компонентах hour і minutes * /
time maketime (int hour, int minutes) {
time temp;
temp.hour = hour;
temp.minutes = minutes;
return temp;
}
Зауважимо: ніякого конфлікту між ім'ям аргументу і ім'ям елемента структури не виникає, більше того, схожість підкреслює спорідненість позначаються їм об'єктів.
Тепер за допомогою maketime можна виконувати динамічну ініціалізацію структури або формувати структурні аргументи для тієї чи іншої функції:
chronos timer;
timer.begin = maketime (0, 0);
timer.end = maketime (12, 5);
Наступний крок полягає у визначенні ряду функцій, що реалізують різні операції над часом. В якості прикладу розглянемо наступну функцію:
/ * Addtime: додавання часу * /
time addtime (time tm1, time tm2)
{
tm1.minutes + = tm2.minutes;
tm1.hour + = tm2.hour + tm1.minutes/60;
tm1.minutes% = 60;
return tm1;
}
Тут обидва аргументи і повертається значення - структури.
В якості іншого прикладу наведемо функцію tinchronos, яка перевіряє: чи знаходиться даний момент часу всередині нашого інтервалу.
/ * Tinchronos: повертає 1, якщо t в c, і 0 у противному випадку * /
int tinchronos (struct time t, struct chronos c)
{
return t.hour> = c.begin.hour
& & T.hour <c.end.hour
& & T.minutes> = c.begin.minutes
& & T.minutes <c.end.minutes;
}
Покажчики на структури
Оскільки ім'я структурного типу володіє всіма правами імен типів, те дозволено визначати покажчики на структури:імя_структурного_тіпа * імя_указателя_на_структуру;
Якщо функції передається велика структура, те, чим копіювати її цілком, ефективніше передати вказівник на неї. Покажчики на структури нічим не відрізняються від покажчиків на звичайні змінні. Оголошення
time * pt;
повідомляє, що pt - це покажчик на структуру типу struct time. Якщо pt вказує на структуру time, то * pt - це сама структура, а (* pt). Hour і (* pt). Minutes - її елементи. Використовуючи покажчик pt, ми могли б написати
time origin, * pt;
pt = &origin;
printf ("origin: (% d,% d) \ n", (* pt). hour, (* pt). minutes);
Дужки в (* pt). Hour необхідні, оскільки пріоритет операції «." Вище, ніж пріоритет операції разименованія «*». Вираз * pt.hour буде проінтерпретувати як * (pt.hour), що невірно, оскільки pt.hour не є покажчиком.
Покажчики на структури використовуються дуже часто, тому для доступу до її елементів була придумана операція «звернення до елементу структури за вказівником», скорочено «стрілка» з формою запису «->». Якщо t - покажчик на структуру, то
t-> елемент-структури
є її окремий елемент. Тому printf можна переписати у вигляді
printf ("origin: (% d,% d) \ n", pt-> hour, pt-> minutes);
Операції. і -> левоассоціатівни, тобто виконуються зліва направо. Таким чином, при наявності оголошення
chronos ch, * cht = &ch;
наступні чотири вираження будуть еквівалентні:
ch.begin.hour
cht-> begin.hour
(Ch.begin). Hour
(Cht -> begin). Hour
Операції доступу до елементів структури. і -> разом з операторами виклику функції () та індексації масиву [] займають найвище положення в ієрархії пріоритетів та виконуються раніше будь-яких інших операторів. Наприклад, якщо задано оголошення
struct {
int len;
char * str;
} * P;
то
+ + P-> len
збільшить на 1 значення елемента структури len, а не покажчик p, оскільки в цьому виразі як би неявно присутні дужки: + + (p-> len). Щоб змінити порядок виконання операцій, потрібні явні дужки. Так, у (+ + р) -> len, перш ніж узяти значення len, програма збільшить покажчик p. В (р ++)-> len покажчик p збільшиться після того, як буде взято значення len (в останньому випадку дужки не обов'язкові).
За тими ж правилами * p-> str позначає вміст об'єкта, на який вказує str; * p-> str + + збільшить покажчик str після отримання значення об'єкта, на який він вказував (як і в вираженні * s + +), (* p-> str ) + + збільшить значення об'єкта, на який вказує str; * p + + -> str збільшить p після отримання того, на що вказує str.
Часто виникає проблема, при оголошенні структури оголосити там покажчик на цю ж структуру. Не дивлячись на те, що опис структури ще не завершено, формат мови це дозволяє. Наприклад, опишемо структуру List, що представляє собою односпрямований список, де в якості даних опишемо змінну типу int.
struct List {
int dat;
List * next;
};
Якщо структури містяться один в одному, то використовують предоб'явленіе структури. Наприклад
struct B;
struct A {B b;};
struct B {A a;};
Розглянемо приклад програми створює такий список і виводить його вміст на консоль.
# Include <stdio.h>
struct List
{
int dat;
List * next;
};
void main ()
{
int i;
List * p, * heap = new List;
for (p = heap, i = 0; i <10; i + +) {
p-> dat = i;
p = p-> next = new List;
}
for (p = heap, i = 0; i <10; i + +) {
printf ("% d", p-> dat);
p = p-> next;
}
}
Тут ми описали два покажчики: heap - для вказівки початку списку, p - для пересування за списком; і просту змінну, як лічильник циклу. На відміну від масиву, наш список буде "розкиданий" по пам'яті, оскільки оператор new виділяє перші вільні блоки пам'яті, але це неважливо, оскільки ми пересуваємося за списком, використовуючи збережені в самому списку адреси:
p = p-> next;.
Масиви структур
Розглянемо програму, що визначає число входжень кожного ключового слова в текст Сі-програми. Нам потрібно вміти зберігати ключові слова у вигляді масиву рядків і лічильники ключових слів у вигляді масиву цілих. Один з можливих варіантів - це мати два паралельних масиву:char * keyword [NKEYS];
int keycount [NKEYS];
Однак саме той факт, що вони є паралельними, підказує нам іншу організацію зберігання - через масив структур. Кожне ключове слово можна описати парою характеристик
char * word;
int count;
Такі пари складають масив. Оголошення
struct key {
char * word;
int count;
} Keytab [NKEYS];
оголошує структуру типу key і визначає масив keytab, кожен елемент якого є структурою цього типу і якому десь буде виділена пам'ять. Це ж можна записати й по-іншому:
struct key {
char * word;
int count;
};
key keytab [NKEYS];
Так як keytab містить постійний набір імен, його найлегше зробити зовнішнім масивом і ініціалізувати один раз на момент визначення. Ініціалізація структур аналогічна раніше демонстрованих ініціалізації - за визначенням слід список ініціалізаторов, укладений у фігурні дужки:
struct key {
char * word;
int count;
} Keytab [] = {
"Auto", 0,
"Break", 0,
"Case", 0,
"Char", 0,
"Const", 0,
"Continue", 0,
"Default", 0,
/*...*/
"Unsigned", 0,
"Void", 0,
"Volatile", 0,
"While", 0
};
Ініціалізатор задаються парами, щоб відповідати конфігурації структури. Строго кажучи, пару ініціалізаторов для кожної окремої структури варто було б укласти у фігурні дужки, як, наприклад, в
{"Auto", 0},
{"Break", 0},
{"Case", 0},
...
Однак коли ініціалізатор - прості константи або рядки символів і всі вони є в наявності, у внутрішніх дужках немає необхідності. Кількість елементів масиву keytab буде обчислено за кількістю ініціалізаторов, оскільки вони представлені повністю, а всередині квадратних дужок "[]" нічого не задано.
Програма підрахунку ключових слів починається з визначення keytab. Програма main читає введення, багаторазово звертаючись до функції getword і отримуючи на кожному її виклику чергове слово. Кожне слово шукається в keytab. Для цього використовується функція бінарного пошуку. Список ключових слів повинен бути впорядкований в алфавітному порядку.
# Include <stdio.h>
# Include <ctype.h>
# Include <string.h>
# Define MAXWORD 100
int getword (char *, int);
int binsearch (char *, struct key *, int);
/ * Підрахунок ключових слів Сі * /
main ()
{
int n;
char word [MAXWORD];
while (getword (word, MAXWORD)! = EOF)
if (isalpha (word [0]))
if ((n = binsearch (word, keytab, NKEYS))> = 0)
keytab [n]. count + +;
for (n = 0; n <NKEYS; n + +)
if (keytab [n]. count> 0)
printf ("% 4d% s \ n", keytab [n]. count, keytab [n]. word);
return 0;
}
/ * Binsearch: знайти слово в tab [0] ... tab [n-1] * /
int binsearch (char * word, struct key tab [], int n)
{
int cond;
int low, high, mid;
low = 0;
high = n-1;
while (low <= high) {
mid = (low + high) / 2;
if ((cond = strcmp (word, tab [mid]. word)) <0)
high = mid - 1;
else if (cond> 0)
low = mid + 1;
else
return mid;
}
return -1;
}
Трохи пізніше ми розглянемо функцію getword, а зараз нам досить знати, що при кожному її виклику виходить чергове слово, яке запам'ятовується в масиві, заданому першим аргументом.
NKEYS - кількість ключових слів у keytab. Хоча ми могли б підрахувати число таких слів вручну, набагато легше і безпечніше зробити це з допомогою машини, особливо якщо список ключових слів може бути змінений. Одне з можливих рішень - помістити в кінець списку ініціалізаторов порожній покажчик (NULL) і потім перебирати в циклі елементи keytab, поки не зустрінеться кінцевий елемент.
Але можливе й більш просте рішення. Оскільки розмір масиву повністю визначений під час компіляції і дорівнює добутку кількості елементів масиву на розмір його окремого елемента, число елементів масиву можна обчислити за формулою
розмір keytab / розмір struct key
У Сі є унарна операція sizeof, яка працює під час компіляції. Його можна застосовувати для обчислення розміру будь-якого об'єкта. Вирази
sizeof об'єкт
і
sizeof (ім'я типу)
видають цілі значення, рівні розміру зазначеного об'єкта або типу в байтах. (Строго кажучи, sizeof видає беззнаковое ціле, тип якого size_t визначена заголовному файлі <stddef.h>.) Що стосується об'єкта, то це може бути змінна, масив або структура. Як ім'я типу може виступати ім'я базового типу (int, double ...) або ім'я похідного типу, наприклад структури або покажчика.
У нашому випадку, щоб обчислити кількість ключових слів, розмір масиву треба поділити на розмір одного елемента. Зазначене обчислення використовується в інструкції # define для встановлення значення NKEYS:
# Define NKEYS (sizeof keytab / sizeof (struct key))
Цей же результат можна отримати іншим способом - поділити розмір масиву на розмір якогось його конкретного елемента:
# Define NKEYS (sizeof keytab / sizeof keytab [0])
Перевага такого роду записів у тому, що їх не треба коppектіровать при зміні типу.
Оскільки препроцесор не звертає уваги на імена типів, оператор sizeof не можна застосовувати в # if. Але в # define вираз препроцесором не обчислюється, так що запропонована нами запис допустима.
Тепер поговоримо про функції getword. Ми написали getword в кілька більш загальному вигляді, ніж потрібно для нашої програми, але вона від цього не стала помітно складніше. Функція getword бере з вхідного потоку наступне "слово". Під словом розуміється ланцюжок літер-цифр, що починається з букви, або окремий символ, відмінний від символу-роздільника. У разі кінця файла функція повертає EOF, в решті випадків її значенням є код першого символу слова або сам символ, якщо це не буква.
/ * Getword: приймає наступне слово або символ, які вводить * /
int getword (char * word, int lim)
{
int c, getch (void);
void ungetch (int);
char * w = word;
while (isspace (c = getch ()))
;
if (c! = EOF)
* W + + = c;
if (! isalpha (c)) {
* W = '\ 0';
return c;
}
for (; - lim> 0; w + +)
if (! isalnum (* w = getch ())) {
ungetch (* w);
break;
}
* W = '\ 0';
return word [0];
}
Функція getword звертається до getch і ungetch. По завершенні набору літер-цифр виявляється, що getword взяла зайвий символ. Звернення до ungetch дозволяє повернути його назад у вхідний потік. У getword використовуються також isspace - для пропуску символів-роздільників, isalpha - для ідентифікації букв і isalnum - для розпізнавання букв-цифр. Всі вони описані в стандартному заголовному файлі <ctype.h>.
Об'єднання схожі на структури, але виконують дещо інші функції. В об'єднанні всі змінні починаються з однієї адреси, вони поєднані в пам'яті, що дозволяє інтерпретувати одну і ту ж область пам'яті, як дані різного типу. Розмір об'єднання визначається максимальним розміром змінної.
Формат об'єднання відрізняється від структури тільки службовим словом union:
union ім'я {
тип1 ім'я змінної 1;
тип2 ім'я змінної 2;
...
};
Об'єднання, як і структура, визначає новий тип даних і описується, як правило, поза опису функції, а змінні описуються, використовуючи його ім'я як ім'я нового типу. Крапка з комою в кінці опису об'єднання повинна обов'язково бути присутнім.
Доступ до елементів об'єднання здійснюється так само, як до елементів структури - через точку для імені об'єднання, або по стрілці для звернення через покажчик.
Приклад 1. Наприклад, є 4 прапори, і ми хотіли б скоротити час для операцій з кількома прапорами відразу. Для простоти розглянемо, як можна обнулити всі прапори однією операцією:
union Flag {
long g;
char ch [4];
};
void main ()
{
Flag fl;
fl.ch [0] = 1;
fl.ch [1] = 2;
fl.ch [2] = 4;
fl.ch [3] = 8;
printf ("Flag =% x \ n", fl.g);
fl.g = 0; / / Всі прапори рівні 0
printf ("Flag = NULL \ n");
for (int i = 0; i <4; i + +)
printf ("% d \ n", (int) fl.ch [i]);
}
Ми описали об'єднання, як змінну типу long і, одночасно, у вигляді масиву типу char. Тепер, для змінної типу Flag, ми можемо працювати з кожним прапором незалежно, чи, використовуючи операцію зі змінною типу long, обнулити всі прапори простий операцією привласнення fl.g = 0;.
У наступному операторі висновку ми хотіли вивести кожен символ у вигляді цілого числа, тому ми поставили оператор явного перетворення типу: (int) fl.ch [i].
- Функцію, яка розміщує структуру в пам'яті і повертає вказівник на неї;
- Функцію, що видаляє структуру з пам'яті;
- Функцію для установки полів структури, наприклад:
- Функції, які повертають значення полів, наприклад:
- Функцію для перегляду структури (виведення значень її полів).
Розмістити структури у динамічній пам'яті, об'єднавши їх в список. Написати всі необхідні функції для роботи зі списком:
- Функцію, що додає структуру в список;
- Функцію, що видаляє структуру зі списку;
- Функцію, повертає кількість елементів у списку.
Написати функцію, що виконує запит (приклад запиту для кожного варіанта наведено в таблиці). Зберегти список у файлі.
Таблиця.
Приклади варіантів
2. Керніган Б., Рітчі Д. Мова програмування Сі. М.: Фінанси і статистика, 1992. - 272с.
3. Подбельський В. В., Фомін С. С. Програмування на мові Сі. Учеб.пособие. М.: Фінанси і статистика, 2004. 600 с.
У нашому випадку, щоб обчислити кількість ключових слів, розмір масиву треба поділити на розмір одного елемента. Зазначене обчислення використовується в інструкції # define для встановлення значення NKEYS:
# Define NKEYS (sizeof keytab / sizeof (struct key))
Цей же результат можна отримати іншим способом - поділити розмір масиву на розмір якогось його конкретного елемента:
# Define NKEYS (sizeof keytab / sizeof keytab [0])
Перевага такого роду записів у тому, що їх не треба коppектіровать при зміні типу.
Оскільки препроцесор не звертає уваги на імена типів, оператор sizeof не можна застосовувати в # if. Але в # define вираз препроцесором не обчислюється, так що запропонована нами запис допустима.
Тепер поговоримо про функції getword. Ми написали getword в кілька більш загальному вигляді, ніж потрібно для нашої програми, але вона від цього не стала помітно складніше. Функція getword бере з вхідного потоку наступне "слово". Під словом розуміється ланцюжок літер-цифр, що починається з букви, або окремий символ, відмінний від символу-роздільника. У разі кінця файла функція повертає EOF, в решті випадків її значенням є код першого символу слова або сам символ, якщо це не буква.
/ * Getword: приймає наступне слово або символ, які вводить * /
int getword (char * word, int lim)
{
int c, getch (void);
void ungetch (int);
char * w = word;
while (isspace (c = getch ()))
;
if (c! = EOF)
* W + + = c;
if (! isalpha (c)) {
* W = '\ 0';
return c;
}
for (; - lim> 0; w + +)
if (! isalnum (* w = getch ())) {
ungetch (* w);
break;
}
* W = '\ 0';
return word [0];
}
Функція getword звертається до getch і ungetch. По завершенні набору літер-цифр виявляється, що getword взяла зайвий символ. Звернення до ungetch дозволяє повернути його назад у вхідний потік. У getword використовуються також isspace - для пропуску символів-роздільників, isalpha - для ідентифікації букв і isalnum - для розпізнавання букв-цифр. Всі вони описані в стандартному заголовному файлі <ctype.h>.
2. Об'єднання
Об'єднання - це змінна, яка може містити (у різні моменти часу) об'єкти різних типів і розмірів. Всі вимоги щодо розмірів і вирівнювання виконує компілятор. Об'єднання дозволяють зберігати різнорідні дані в одній і тій же області пам'яті без включення в програму машинно-залежної інформації. Ці кошти аналогічні варіантним записам у Паскалі.Об'єднання схожі на структури, але виконують дещо інші функції. В об'єднанні всі змінні починаються з однієї адреси, вони поєднані в пам'яті, що дозволяє інтерпретувати одну і ту ж область пам'яті, як дані різного типу. Розмір об'єднання визначається максимальним розміром змінної.
Формат об'єднання відрізняється від структури тільки службовим словом union:
union ім'я {
тип1 ім'я змінної 1;
тип2 ім'я змінної 2;
...
};
Об'єднання, як і структура, визначає новий тип даних і описується, як правило, поза опису функції, а змінні описуються, використовуючи його ім'я як ім'я нового типу. Крапка з комою в кінці опису об'єднання повинна обов'язково бути присутнім.
Доступ до елементів об'єднання здійснюється так само, як до елементів структури - через точку для імені об'єднання, або по стрілці для звернення через покажчик.
Приклад 1. Наприклад, є 4 прапори, і ми хотіли б скоротити час для операцій з кількома прапорами відразу. Для простоти розглянемо, як можна обнулити всі прапори однією операцією:
union Flag {
long g;
char ch [4];
};
void main ()
{
Flag fl;
fl.ch [0] = 1;
fl.ch [1] = 2;
fl.ch [2] = 4;
fl.ch [3] = 8;
printf ("Flag =% x \ n", fl.g);
fl.g = 0; / / Всі прапори рівні 0
printf ("Flag = NULL \ n");
for (int i = 0; i <4; i + +)
printf ("% d \ n", (int) fl.ch [i]);
}
Ми описали об'єднання, як змінну типу long і, одночасно, у вигляді масиву типу char. Тепер, для змінної типу Flag, ми можемо працювати з кожним прапором незалежно, чи, використовуючи операцію зі змінною типу long, обнулити всі прапори простий операцією привласнення fl.g = 0;.
У наступному операторі висновку ми хотіли вивести кожен символ у вигляді цілого числа, тому ми поставили оператор явного перетворення типу: (int) fl.ch [i].
3. Практичні завдання
Завдання 3.1
Розглянути приклад односпрямованого списку, побудованого на структурі List. Змініть структуру так, щоб отримати можливість пересуватися по списку не тільки вперед, але і назад (двонаправлений список).Завдання 3.2.
Записи в лінійному списку містять ключове поле типу int. Сформувати односпрямований список. Видалити з нього елемент із заданим номером, додати елемент із заданим номером.Завдання 3.3.
Записи в лінійному списку містять ключове поле типу * char (рядок символів). Сформувати двонаправлений список. Видалити елемент із заданим ключем. Додати До елементів перед елементом із заданим номером.4. Лабораторні завдання
Написати програму, в якій необхідно оголосити структуру даних у відповідності з варіантом. Написати всі необхідні функції для роботи зі структурою:- Функцію, яка розміщує структуру в пам'яті і повертає вказівник на неї;
- Функцію, що видаляє структуру з пам'яті;
- Функцію для установки полів структури, наприклад:
- Функції, які повертають значення полів, наприклад:
- Функцію для перегляду структури (виведення значень її полів).
Розмістити структури у динамічній пам'яті, об'єднавши їх в список. Написати всі необхідні функції для роботи зі списком:
- Функцію, що додає структуру в список;
- Функцію, що видаляє структуру зі списку;
- Функцію, повертає кількість елементів у списку.
Написати функцію, що виконує запит (приклад запиту для кожного варіанта наведено в таблиці). Зберегти список у файлі.
Таблиця.
Приклади варіантів
| Варіант | Структура | Поля структури | Приклад запиту |
| 1 | СТУДЕНТ | ім'я - char * | Імена студентів зазначеного курсу |
| курс - int | |||
| підлога - bool | |||
| 2 | СЛУЖБОВЕЦЬ | ім'я - char * | Кількість службовців зі стажем не менше заданого |
| професія - char * | |||
| робочий стаж - int | |||
| 3. | АВТОМОБІЛЬ | марка - char * | Марки автомобілів потужністю не більше заданої |
| потужність - int | |||
| вартість - float | |||
| 4 | КАДРИ | ім'я - char * | Імена робочих заданого розряду |
| номер цеху - int | |||
| розряд - int | |||
| 5 | ЦЕХ | ім'я - char * | Найменування продукції, кількість якої не менше заданого |
| начальник - char * | |||
| к-ть робітників - int | |||
| 6 | ВИРІБ | найменування - char * | Найменування виробів, кількість яких не більше заданого |
| шифр - char * | |||
| кількість - int | |||
| 7 | БІБЛІОТЕКА | ім'я - char * | Кількість книг зазначеного автора |
| автор - char * | |||
| вартість - real | |||
| 8 | ІСПИТ | ім'я студента - char * | Імена студентів, які здавали іспит в заданий день |
| дата - int | |||
| оцінка - int | |||
| 9 | АДРЕСА | ім'я - char * | Імена що живуть на парній стороні заданої вулиці |
| вулиця - char * | |||
| номер будинку - int | |||
| 10 | ТОВАР | ім'я - char * | Найменування товару, вартістю не вище заданої |
| кількість - int | |||
| вартість - real | |||
| 11 | КВИТАНЦІЯ | номер - int | Загальна сума всіх квитанцій вказаної дати |
| дата - int | |||
| сума - real | |||
| 12 | КРАЇНА | назва - char * | Назва країн, площею не менше заданої |
| грошова одиниця - char * | |||
| площа - float | |||
| 13 | ПОЇЗД | номер - char * | Номери всіх поїздів зазначеного типу |
| тип - char * | |||
| к-ть вагонів - int | |||
| 14 | ГРА | найменування - char * | Найменування гри зазначеного типу і з вартістю не вище заданої |
| тип - char * | |||
| вартість - float | |||
| 15 | ПЛАНЕТА | ім'я - char * | Ім'я планет з відстанню від Землі не більше заданої |
| розмір - real | |||
| відстань від Землі - real | |||
| 16 | ТВАРИНА | ім'я - char * клас - char * середня вага - float | Імена всіх тварин заданого класу |
| 17 | ФОТОАПАРАТ | модель - char * | Моделі фотоапаратів з розміром матриці не менше заданої |
| виробник - char * | |||
| розмір матриці - int | |||
| 18 | КОРАБЕЛЬ | ім'я - char * | Середнє водотоннажність кораблів заданого типу |
| тип - char * | |||
| водотоннажність - int | |||
| 19 | РІЧКА | ім'я - char * | Середню довжину річки на зазначеному континенті |
| континент - char * | |||
| довжина - float | |||
| 20 | СТРАВА | назва - char * | Загальну вартість замовлення |
| тип - char * | |||
| вартість - float |
5. Додаткові завдання
Завдання 5.1.
Напишіть програму, яка читає текст Сі-програми і друкує в алфавітному порядку всі групи імен змінних, у яких збігаються перші 6 символів, але подальші в чомусь різняться. Не обробляйте нутрощі узяті в лапки рядків і коментарів. Число 6 зробіть параметром, що задається в командному рядку.Завдання 5.2.
Напишіть програму друку таблиці "перехресних посилань", яка буде друкувати всі слова документа і вказувати для кожного з них номери рядків, де воно зустрілося. Програма повинна ігнорувати "шумові" слова, такі як "і", "або" і пр.Завдання 5.3.
Напишіть програму, яка друкує весь набір різних слів, що утворюють вхідний потік, в порядку зростання частоти їхньої зустрічальності. Перед кожним словом має бути зазначено кількість входжень.Бібліографічний список
1. Керніган Б., Рітчі Д., Фьюер А. Мова програмування Сі: Завдання з мови Сі. М.: Фінанси і статистика, 1985. - 192с.2. Керніган Б., Рітчі Д. Мова програмування Сі. М.: Фінанси і статистика, 1992. - 272с.
3. Подбельський В. В., Фомін С. С. Програмування на мові Сі. Учеб.пособие. М.: Фінанси і статистика, 2004. 600 с.